/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-1-bits
   @Language: C++
   @Datetime: 19-05-13 13:49
   */


// Method 1, Time 327ms
class Solution {
public:
	/**
	 * @param n: an unsigned integer
	 * @return: the number of '1' bits
	 */
	int hammingWeight(unsigned int n) {
		// write your code here
		int bit=0;
		for(; n; n=n&(n-1))
			++bit;
		return bit;
	}
};


// Method 2, search table, Time 101ms
class Solution {
public:
	/**
	 * @param n: an unsigned integer
	 * @return: the number of '1' bits
	 */
	int hammingWeight(unsigned int n) {
		// write your code here
		int bit=0;
		int bits[]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
		for(; n; n>>=4)
			bit+=bits[n&0xF];
		return bit;
	}
};
